//package leecode;
//
//import java.util.ArrayList;
//import java.util.Arrays;
//import java.util.HashSet;
//import java.util.List;
//import java.util.Set;
//
///**
// * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
// * 
// * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
// * 
// * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
// * 
// * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/n-queens
// * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
// */
//public class _51_solveNQueens {
//
//	public static void main(String[] args) {
//		System.out.println(new _51_solveNQueens().solveNQueens(4));
//	}
//
//	public List<List<String>> solveNQueens(int n) {
//		// 如果 x 相等则同一行， y 相等则同一列， 如果 y 坐标 与 x 坐标的差值 相等则表示斜方向在同一行
//		List<int[]> indexArrList = new ArrayList<>();
//		// 深度优先搜索: 一开始从第 0 行选择一个点，共循环 n 次数
//		int[] indexArr = new int[n];
//		// 从 indexArr 的第 x 行选择一个符合要求的数值
//		for (int i = 0; i < n; i++) {
//			indexArr[i] = -1;
//			select(indexArr, i);
//		}
//		// 如果符合要求则 add 一次
//		System.out.println(Arrays.toString(indexArr));
//		indexArrList.add(indexArr);
//		return toList(indexArrList);
//    }
//
//	private void select(int[] indexArr, int i) {
//		int m = -1;
//		for (int j = 0; j < indexArr.length; j++) {
//			// 需要满足 纵向不等 和 对角线不等
//			boolean checked = false; 
//			for (int k = 0; k < i; k++) {
//				// k, indexArr[k], 而本次取值为 i, j
//				// 纵向不等
//				if (indexArr[k] == j) {
//					checked = true;
//					break;
//				}
//				// 对角线不等
//				int xie = (indexArr[k] - j) / (k - i);
//				if (xie == 1 || xie == -1) {
//					checked = true;
//					break;
//				}
//			}
//			if (!checked) {
//				System.out.println(111);
//				m = j;
//				break;
//			}
//		}
//		if (m != -1) {
//			indexArr[i] = m;emmet
//		}
//	}
//
//	private List<List<String>> toList(List<int[]> indexArrList) {
//		List<List<String>> list = new ArrayList<>(indexArrList.size());
//		for (int[] indexArr : indexArrList) {
//			List<String> list1 = new ArrayList<>(indexArr.length);
//			for (int i = 0; i < indexArr.length; i++) {
//				StringBuilder sb = new StringBuilder();
//				for (int j = 0; j < indexArr.length; j++) {
//					sb.append(indexArr[i] == j ? "Q" : ".");
//				}
//				list1.add(sb.toString());
//			}
//			list.add(list1);
//		}
//		return list;
//	}
//}
